package lib

//link to 53,503
func init() {
	Probs = append(Probs, Problem{
		Num:         918,
		Discription: "循环数组的最大子数组之和",
		Level:       2,
		Labels: map[string]int{
			"动态规划":   1,
			"前缀和": 1,
		},
	})
}

//解分为两部分
//一部分是正常数组的子数组的最大和
//另一部分是包含开头一部分和结尾一部分的子数组最大和，开头和结尾的部分可以用前缀和求出最大子数组之和
func MaxSubarraySumCircular(nums []int) int {
	res := nums[0]
	//前缀和
	forwardSum := nums[0]
	//dp[i]表示[:i+1]中正常数组的最大子数组之和
	dp := make([]int, len(nums))
	//在[:i+1]中，以0为起点的最大子数组之和
	leftMax := make([]int, len(nums))
	dp[0] = nums[0]
	leftMax[0] = nums[0]
	for i := 1; i < len(nums); i++ {
		forwardSum += nums[i]
		leftMax[i] = max(leftMax[i-1], forwardSum)
		if dp[i-1] <= 0 {
			dp[i] = nums[i]
		} else {
			dp[i] = dp[i-1] + nums[i]
		}
		res = max(res, dp[i])
	}

	//后缀和
	backwardsSum := 0
	//固定右半边子数组的开始位置，在剩余范围内选出左半边的最大前缀和相加
	for i := len(nums) - 1; i >= 2; i-- {
		backwardsSum += nums[i]
		res = max(res, backwardsSum+leftMax[i-2])
	}

	return res
}